package com.LeeCode;

/**
 * 在链表中插入最大公约数
 */

public class Code2807 {
    public static void main(String[] args) {
        int[] arr = {18, 6, 10, 3};
        ListNode head = Utils.arrayToListNode(arr);
        Utils.printListNode(new Code2807().insertGreatestCommonDivisors(head));
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null) {
            int num = gcd(slow.val, fast.val);
            ListNode temp = new ListNode(num);
            slow.next = temp;
            temp.next = fast;
            slow = fast;
            fast = fast.next;
        }
        return head;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int temp = a;
            a = b % a;
            b = temp;
        }
        return b;
    }
}
